package com.cn.algorithm02.class13;

import com.cn.algorithm02.class01.Nodea;

/***
 * @author: hels
 * 是不是满二叉树
 * 高度h，节点数为2^n-1
 *  二叉树的动态规划问题
 **/
public class C05_IsFBT {
    public static void main(String[] args) {
        int[] arr = {6,3,9,2,5,7,1};
        Nodea head = Nodea.getNodeInstance(arr);
        head.left = null;
        Nodea.printTree(head);
        System.out.println(isFBT(head));

    }

    public static boolean isFBT(Nodea head) {

        return checkMethod(process(head));
    }

    public static Info process(Nodea x) {
        if (x == null) return new Info(0, 0);

        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        int nums = 1;
        if (leftInfo != null) {
            nums += leftInfo.nums ;
        }
        if (rightInfo != null) {
            nums += rightInfo.nums;
        }
        return new Info(height, nums);
    }

    public static boolean checkMethod(Info info) {
        return ((1 << info.height) - 1) == info.nums ;
    }


    public static class Info {
        int height; // 当前节点的高度
        int nums;   // 当前节点包含的节点数量（包括父节点）
        public Info(int height, int nums) {
            this.height = height;
            this.nums = nums;
        }
    }

}
